package leetcode;

import java.util.*;

public class Solution {
    public int mostFrequentEven(int[] nums) {
        int len = 0, n = nums.length, res = -1;
        Arrays.sort(nums);
        for (int i = 0; i < n; i++)
            if (nums[i] % 2 == 0) {
                int j = i + 1;
                while (j < n && nums[j] == nums[i] && nums[j] % 2 == 0) j++;
                if (j - i > len) {
                    len = j - i;
                    res = nums[i];
                }
                if (j == n) break;
                i = j - 1;
            }
        return res;
    }

    public double trimMean(int[] arr) {
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        int len = arr.length;
        int step = (len * 5) / 100;
        int sum = 0;
        for (int i = step; i < len - step; i++) {
            sum += arr[i];
        }
        return (double) sum / (len - 2 * step);
    }

    public void order1() {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        if (num % 2 == 0) {
            System.out.println(num - 5);
        } else {
            System.out.println(-num);
        }
    }

    /**
     * 2432.处理用时最长的那个任务的员工
     *
     * @param n
     * @param logs
     * @return
     */
    public int hardestWorker(int n, int[][] logs) {
        int[] max = {0, logs[0][1]};
        for (int i = 1; i < logs.length; i++) {
            int time = logs[i][1] - logs[i - 1][1];
            if (time > max[1]) {
                max[0] = i;
                max[1] = time;
            } else if (time == max[1]) {
                // 时间相同，比较id
                int currentMaxId = logs[max[0]][0];
                if (logs[i][0] < currentMaxId) {
                    // 修改id
                    max[0] = i;
                }
            }
        }
        return logs[max[0]][0];
    }

    /**
     * 2433. 找出前缀异或的原始数组
     *
     * @param pref 整数数组
     * @return
     */
    public int[] findArray(int[] pref) {
        /**
         * dp[i] = pref[i] ^ pref[i - 1];
         */
        int dp[] = new int[pref.length];
        dp[0] = pref[0];
        for (int i = 1; i < pref.length; i++) {
            dp[i] = pref[i] ^ pref[i - 1];
        }
        return dp;
    }

    /**
     * 1441.用栈构建数组
     *
     * @param target
     * @param n
     * @return
     */
    public List<String> buildArray(int[] target, int n) {
        List<String> res = new ArrayList<>();
        int i = 0, j = 1;
        while (i < target.length && j <= n) {
            if (target[i] == j) {
                res.add("Push");
                j++;
                i++;
            } else {
                int step = Math.abs(target[i] - j);
                for (int k = 0; k < step; k++) {
                    res.add("Push");
                    res.add("Pop");
                }
                j += step;
            }
        }
        return res;
    }

    /**
     * 886. 可能的二分法（广度优先搜索，深度优先搜索）
     *
     * @param n
     * @param dislikes
     * @return
     */
    public boolean possibleBipartition(int n, int[][] dislikes) {
        boolean res = false;
        List<Integer> group1 = new ArrayList<>();
        List<Integer> group2 = new ArrayList<>();
        group1.add(dislikes[0][0]);
        group2.add(dislikes[0][1]);
        return res;
    }

    /**
     * 779.第K个语法符号
     *
     * @param n
     * @param k
     * @return
     */
    public int kthGrammar(int n, int k) {
        if (n == 1) {
            return 0;
        }
        return (k & 1) ^ 1 ^ kthGrammar(n - 1, (k + 1) / 2);
    }


    /**
     * 数组范围求和
     *
     * @param nums
     * @param start
     * @param end
     * @return
     */
    public int sumNumRange(int[] nums, int start, int end) {
        int sum = 0;
        for (int i = start; i <= end; i++) {
            sum += nums[i];
        }
        return sum;
    }

    /**
     * 862.和至少为K的最短子数组
     *
     * @param nums
     * @param k
     * @return
     */
    public int shortestSubarray(int[] nums, int k) {
        // 初始化窗口大小为 1
        int window = 1;
        while (window <= nums.length) {
            int left = 0;
            int right = window - 1;
            while (right < nums.length) {
                int sum = sumNumRange(nums, left, right);
                if (sum >= k) {
                    return right - left + 1;
                }
                left++;
                right++;
            }
            window++;
        }
        return -1;
    }

    /**
     * 1704.判断字符串的两半是否相似
     */
    public boolean halvesAreAlike(String s) {
        String a = s.substring(0, s.length() / 2);
        String b = s.substring(s.length() / 2);
        String t = "aeiouAEIOU";
        int sum1 = 0;
        int sum2 = 0;
        for (int i = 0; i < a.length(); i++) {
            if (t.indexOf(a.charAt(i)) >= 0) {
                sum1++;
            }
        }
        for (int i = 0; i < b.length(); i++) {
            if (t.indexOf(b.charAt(i)) >= 0) {
                sum2++;
            }
        }
        return sum1 == sum2;
    }

    public static int countBalls(int lowLimit, int highLimit) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = lowLimit; i <= highLimit; i++) {
            int sum = 0;
            int temp = i;
            while (temp >= 1) {
                int num = temp % 10;
                sum += num;
                temp /= 10;
            }
            if (map.containsKey(sum)) {
                map.put(sum, map.get(sum) + 1);
            } else {
                map.put(sum, 1);
            }
        }
        int max = 0;
        for (int key : map.keySet()) {
            if (map.get(key) > max) {
                max = map.get(key);
            }
        }
        return max;
    }

    /**
     * 生成交替二进制字符串的最少操作数
     *
     * @param s
     * @return
     */
    public int minOperations(String s) {
        int res0 = 0, res1 = 0;
        // 0100 -> 1010 || 0101
        // 01100 -> 01010 || 10101
        char x = '0';
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == x) {
                res1++;
            } else {
                res0++;
            }
            x ^= 1;
        }
        return Math.min(res0, res1);
    }

    /**
     * 1457.商品折扣后的最终价格
     * 单调栈
     *
     * @param prices
     * @return
     */
    public int[] finalPrices(int[] prices) {
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
                prices[stack.pop()] -= prices[i];
            }
            stack.push(i);
        }
        return prices;
    }

    /**
     * 28.找出字符串中第一个匹配项的下标
     *
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {
        // 暴力匹配
        int i = 0, j = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }
        if (j == needle.length()) {
            return i - j;
        } else {
            return -1;
        }
    }

    public boolean repeatedSubstringPattern(String s) {
        // 旋转字符串判断是否相等
        int i = 0;
        String temp = s;
        while (i < s.length() - 1) {
            StringBuffer buffer = new StringBuffer(temp.substring(1));
            buffer.append(temp.charAt(0));
            if (s.equals(buffer.toString())) {
                return true;
            }
            temp = buffer.toString();
            i++;
        }
        return false;
    }

    /**
     * 逆波兰表达式求值
     *
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        while (stack.isEmpty() || i < tokens.length) {
            if (!tokens[i].equals("+") && !tokens[i].equals("-") && !tokens[i].equals("*") && !tokens[i].equals("/")) {
                stack.push(Integer.parseInt(tokens[i]));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                stack.push(calculate(num1, num2, tokens[i]));
            }
            i++;
        }
        return stack.pop();
    }

    /**
     * 返回两数的操作结果
     *
     * @param num1
     * @param num2
     * @param operator 运算符
     * @return
     */
    public int calculate(int num1, int num2, String operator) {
        return 1;
//        return switch (operator) {
//            case "+" -> num1 + num2;
//            case "-" -> num1 - num2;
//            case "*" -> num1 * num2;
//            default -> num1 / num2;
//        };
    }

    public List<Integer> addToArrayForm(int[] num, int k) {
        int i = num.length - 1;
        while (k >= 1) {
            int n = k % 10;
            int sum = num[i] + n;
            if (i == 0) {
                num[i] = sum;
            } else {
                num[i] = sum % 10;
                num[i - 1] += sum / 10;
            }
            k /= 10;
            i--;
        }
        List<Integer> res = new ArrayList<>();
        for (int n : num) {
            if (n >= 10) {
                res.add(n / 10);
                res.add(n % 10);
            } else {
                res.add(n);
            }
        }
        return res;
    }

    /**
     * 1367. 二叉树中的链表
     *
     * @param head
     * @param root
     * @return
     */
    public boolean isSubPath(ListNode head, TreeNode root) {
        if (head == null) {
            return true;
        }
        if (root == null) {
            return false;
        }
        return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }

    public boolean dfs(ListNode current, TreeNode root) {
        if (current == null) {
            return true;
        }
        if (root == null) {
            return false;
        }
        if (root.val != current.val) {
            return false;
        }
        return dfs(current.next, root.left) || dfs(current.next, root.right);
    }

    /**
     * 字符串中第二大的数字
     *
     * @param s
     * @return
     */
    public int secondHighest(String s) {
        return 0;
    }

    public boolean checkIfPangram(String sentence) {
//        Set<Character> set = new HashSet<>();
//        for (int i = 0; i < sentence.length(); i++) {
//            set.add(sentence.charAt(i));
//        }
//        return set.size() == 26;
        int sum = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < sentence.length(); i++) {
            if (!map.containsKey(sentence.charAt(i))) {
                map.put(sentence.charAt(i), 1);
                sum++;
            }
        }
        return sum == 26;
    }

    public int getLucky(String s, int k) {
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            sum += add(s.charAt(i) - 96);
        }
        for (int j = 0; j < k - 1; j++) {
            sum = add(sum);
        }
        return sum;
    }

    public int add(int num) {
        int sum = 0;
        while (num > 9) {
            sum += num % 10;
            num /= 10;
        }
        return sum + num;
    }

    /**
     * 构成特定和需要添加的最少元素
     *
     * @param nums
     * @param limit
     * @param goal
     * @return
     */
    public int minElements(int[] nums, int limit, int goal) {
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }
        long poor = Math.abs(goal - sum);
        return (int) ((poor + limit - 1) / limit);
    }

    /**
     * 2500.删除每行中的最大值
     *
     * @param grid
     * @return
     */
    public int deleteGreatestValue(int[][] grid) {
        int res = 0;
        for (int[] item : grid) {
            Arrays.sort(item);
        }
        for (int j = 0; j < grid[0].length; j++) {
            int max = 0;
            for (int k = 0; k < grid.length; k++) {
                max = Math.max(max, grid[j][k]);
            }
            res += max;
        }
        return res;
    }

    public int similarPairs(String[] words) {
        ArrayList<HashMap<Character, Integer>> wordMap = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            HashMap<Character, Integer> map = new HashMap<>();
            for (int j = 0; j < words[i].length(); j++) {
                char c = words[i].charAt(i);
                if (!map.containsKey(c)) {
                    map.put(c, 1);
                }
            }
            wordMap.add(map);
        }
        for (int k = 0; k < wordMap.size() - 1; k++) {
            for (int m = k + 1; m < wordMap.size(); m++) {
            }
        }
        return 0;
    }

    public int closetTarget(String[] words, String target, int startIndex) {
        int i = startIndex + 1;
        int n = words.length;
        int res = -1;
        while (i % n != startIndex) {
            if (words[i % n].equals(target)) {
                if (res <= 0) {
                    res = Math.abs(startIndex - i % n);
                } else {
                    res = Math.min(Math.abs(startIndex - i % n), res);
                }
            }
            i++;
        }
        int j = startIndex - 1 + n;
        while (j % n != startIndex) {
            if (words[j % n].equals(target)) {
                if (res < 0) {
                    res = n - Math.abs(startIndex - j % n) - 1;
                } else {
                    res = n - Math.min(Math.abs(startIndex - j % n), res) - 1;
                }
            }
            j = j - 1 + n;
        }
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] words = {"a", "b", "leetcode"};
        String target = "leetcode";
        int startIndex = 0;
        System.out.println(solution.closetTarget(words, target, startIndex));
    }
}
